package KMP算法;

public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        String haystack = "hello";
        String needle = "ll";
        int result = solution.strStr(haystack, needle);
        System.out.println(result); // 应输出 2
    }

    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0; // 如果 needle 是空字符串，返回 0
        if (haystack.isEmpty()) return -1; // 如果 haystack 是空且 needle 不是空，返回 -1
        // 获取next数组
        int[] next = new int[needle.length()];
        getNext2(next, needle);
        // 进行KMP算法匹配
        int i = 0, j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j - 1] + 1; // Fix: Adjust the value to be next[j - 1] + 1
            }
        }
        // 完全匹配 needle 的情况
        if (j == needle.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    // 采用减一策略得到next数组
    public void getNext2(int[] next, String s) {
        int j = -1; // i是后缀的末尾,j是前缀的末尾
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            // 不相等,回滚
            while (j > -1 && s.charAt(i) != s.charAt(j + 1)) j = next[j];
            // 相等时
            if (s.charAt(i) == s.charAt(j + 1)) j++;
            next[i] = j;
        }
    }
}